package leetcode;
import java.util.*;
/**
 * 332.重新安排行程
 * 给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
 * 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。
 * 如果存在多种有效的行程，请你按字典排序返回最小的行程组合
 *
 * 输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
 * 输出：["JFK","MUC","LHR","SFO","SJC"]
 *
 * 输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
 * 输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
 * 解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。
 */
public class Num_332 {

    //建立哈希表存放对应地址
    //K : 索引机场
    //V : 对应机场
    static Map<String, List<String>> map = new HashMap();
    //存放最终结果
    static List<String> ret = new ArrayList<>();
    //存放当前路径
    static List<String> now = new ArrayList<>();
    //建立set表：统计地址的个数
    static Set<String> setCount = new HashSet<>();
    //去重器，存已走过的路径，防止死循环
    static Set<String> setArea = new HashSet<>();

    public static List<String> findItinerary(List<List<String>> tickets) {

        for (int i = 0; i < tickets.size(); i++) {
            //list : ["JFK","SFO"]
            List<String> cur = tickets.get(i);
            //将索引和映射添加到set中
            setCount.add(cur.get(0));
            setCount.add(cur.get(1));
            //存放第i个索引机场对应的全部映射机场
            List<String> values;
            //判断哈希表中是否已存在该索引
            if(!map.containsKey(cur.get(0))){
                values = new ArrayList<>();
            }else{
                values = map.get(cur.get(0));
            }
            //添加映射机场
            values.add(cur.get(1));
            map.put(cur.get(0), values);
        }
        now.add("JFK");
        setArea.add("JFK");
        dfs("JFK");
        return ret;
    }

    private static void dfs(String cur) {
        //边界条件
        if(now.size() == setCount.size()){
            //这是其中一条路线，和上一条路线比较字典序
            if(ret.size() == 0 || compare(ret,now) > 0){
                copy(ret, now);
            }
            return;
        }

        //看之后还能不能走
        if(map.containsKey(cur)){
            List<String> next = map.get(cur);
            for (int i = 0; i < next.size(); i++) {
                //看这个映射有没有走过
                now.add(next.get(i));
                setArea.add(next.get(i));
                dfs(next.get(i));
                now.remove(now.size() - 1);
                setArea.remove(next.get(i));
            }
        }
    }

    //将now的内容覆盖到ret中
    private static void copy(List<String> ret, List<String> now){
        //先清除原有的东西
        ret.clear();
        //再遍历now，添加到ret中
        for (int i = 0; i < now.size(); i++) {
            ret.add(now.get(i));
        }
    }

    //比较字符串数组的字典序, <0则靠前
    private static int compare(List<String> ret, List<String> now){
        for (int i = 0; i < ret.size(); i++) {
            if(ret.get(1).compareTo(now.get(i)) != 0){
                return ret.get(1).compareTo(now.get(i));
            }
        }
        return 0;
    }


    public static void main(String[] args) {
        //tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
        List<String> list = new ArrayList<>();
        List<List<String>> lists = new ArrayList<>();
        list.add("JFK");
        list.add("SFO");
        lists.add(new ArrayList<>(list));
        list.clear();
        list.add("JFK");
        list.add("ATL");
        lists.add(new ArrayList<>(list));
        list.clear();
        list.add("SFO");
        list.add("ATL");
        lists.add(new ArrayList<>(list));
        list.clear();
        list.add("ATL");
        list.add("JFK");
        lists.add(new ArrayList<>(list));
        list.clear();
        list.add("ATL");
        list.add("SFO");
        lists.add(new ArrayList<>(list));
        System.out.println("输入：" + lists.toString());
        List<String> rr = findItinerary(lists);
        System.out.println(rr.toString());
    }
}
